//给定一个未排序的整数数组
// nums ， 返回最长递增子序列的个数 。
//
// 注意 这个数列必须是 严格 递增的。
//
//
//
// 示例 1:
//
//
//输入: [1,3,5,4,7]
//输出: 2
//解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
//
//
// 示例 2:
//
//
//输入: [2,2,2,2,2]
//输出: 5
//解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
//
//
//
//
// 提示:
//
//
//
//
//
// 1 <= nums.length <= 2000
// -10⁶ <= nums[i] <= 10⁶
//
//
// Related Topics 树状数组 线段树 数组与矩阵 动态规划 👍 748 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function findNumberOfLIS(nums: number[]): number {

    /*?
        ? dp[i]：i之前（包括i）最长递增子序列的长度为dp[i]
        ? count[i]：以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]
        ?
    ?*/
    const len = nums.length;
    if(len <= 1) return len;
    let dp = new Array(len).fill(1); //? i之前（包括i）最长递增子序列的长度为dp[i]
    let count = new Array(len).fill(1); //? 以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]
    let res = 0;
    for(let i = 1; i < len; i++){
        for(let j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                if(dp[j] + 1 > dp[i]){ //? 找到一个位置使递增子序列更长
                    dp[i] = dp[j] + 1; //? 更新 dp[i]
                    count[i] = count[j]; //? 重置count[i]
                } else if(dp[j] + 1 === dp[i]){ //? 和原来一样长
                    count[i] += count[j]; //? 更新count[i]
                }
            }
        }
    }
    let max = Math.max(...dp); //? 扩展运算符找到最大长度
    for(let i = 0; i < len; i++) if(dp[i] === max) res += count[i]; //? 累加
    return res;
};
//leetcode submit region end(Prohibit modification and deletion)
